{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Winner on a Tic Tac Toe Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: tictactoe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出井字棋的获胜者"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><em>A</em> 和&nbsp;<em>B</em>&nbsp;在一个&nbsp;<em>3</em>&nbsp;x&nbsp;<em>3</em>&nbsp;的网格上玩井字棋。</p>\n",
    "\n",
    "<p>井字棋游戏的规则如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>玩家轮流将棋子放在空方格 (&quot; &quot;) 上。</li>\n",
    "\t<li>第一个玩家 A 总是用&nbsp;&quot;X&quot; 作为棋子，而第二个玩家 B 总是用 &quot;O&quot; 作为棋子。</li>\n",
    "\t<li>&quot;X&quot; 和 &quot;O&quot; 只能放在空方格中，而不能放在已经被占用的方格上。</li>\n",
    "\t<li>只要有 3 个相同的（非空）棋子排成一条直线（行、列、对角线）时，游戏结束。</li>\n",
    "\t<li>如果所有方块都放满棋子（不为空），游戏也会结束。</li>\n",
    "\t<li>游戏结束后，棋子无法再进行任何移动。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个数组 <code>moves</code>，其中每个元素是大小为 <code>2</code> 的另一个数组（元素分别对应网格的行和列），它按照 <em>A</em> 和 <em>B</em> 的行动顺序（先 <em>A</em> 后 <em>B</em>）记录了两人各自的棋子位置。</p>\n",
    "\n",
    "<p>如果游戏存在获胜者（<em>A</em> 或 <em>B</em>），就返回该游戏的获胜者；如果游戏以平局结束，则返回 &quot;Draw&quot;；如果仍会有行动（游戏未结束），则返回 &quot;Pending&quot;。</p>\n",
    "\n",
    "<p>你可以假设&nbsp;<code>moves</code>&nbsp;都 <strong>有效</strong>（遵循井字棋规则），网格最初是空的，<em>A</em> 将先行动。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]\n",
    "<strong>输出：</strong>&quot;A&quot;\n",
    "<strong>解释：</strong>&quot;A&quot; 获胜，他总是先走。\n",
    "&quot;X  &quot;    &quot;X  &quot;    &quot;X  &quot;    &quot;X  &quot;    &quot;<strong>X</strong>  &quot;\n",
    "&quot;   &quot; -&gt; &quot;   &quot; -&gt; &quot; X &quot; -&gt; &quot; X &quot; -&gt; &quot; <strong>X</strong> &quot;\n",
    "&quot;   &quot;    &quot;O  &quot;    &quot;O  &quot;    &quot;OO &quot;    &quot;OO<strong>X</strong>&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]\n",
    "<strong>输出：</strong>&quot;B&quot;\n",
    "<strong>解释：</strong>&quot;B&quot; 获胜。\n",
    "&quot;X  &quot;    &quot;X  &quot;    &quot;XX &quot;    &quot;XXO&quot;    &quot;XXO&quot;    &quot;XX<strong>O</strong>&quot;\n",
    "&quot;   &quot; -&gt; &quot; O &quot; -&gt; &quot; O &quot; -&gt; &quot; O &quot; -&gt; &quot;XO &quot; -&gt; &quot;X<strong>O</strong> &quot; \n",
    "&quot;   &quot;    &quot;   &quot;    &quot;   &quot;    &quot;   &quot;    &quot;   &quot;    &quot;<strong>O</strong>  &quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]\n",
    "<strong>输出：</strong>&quot;Draw&quot;\n",
    "<strong>输出：</strong>由于没有办法再行动，游戏以平局结束。\n",
    "&quot;XXO&quot;\n",
    "&quot;OOX&quot;\n",
    "&quot;XOX&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>moves = [[0,0],[1,1]]\n",
    "<strong>输出：</strong>&quot;Pending&quot;\n",
    "<strong>解释：</strong>游戏还没有结束。\n",
    "&quot;X  &quot;\n",
    "&quot; O &quot;\n",
    "&quot;   &quot;\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= moves.length &lt;= 9</code></li>\n",
    "\t<li><code>moves[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= moves[i][j] &lt;= 2</code></li>\n",
    "\t<li><code>moves</code>&nbsp;里没有重复的元素。</li>\n",
    "\t<li><code>moves</code> 遵循井字棋的规则。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-winner-on-a-tic-tac-toe-game](https://leetcode.cn/problems/find-winner-on-a-tic-tac-toe-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-winner-on-a-tic-tac-toe-game](https://leetcode.cn/problems/find-winner-on-a-tic-tac-toe-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0],[2,0],[1,1],[2,1],[2,2]]', '[[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]', '[[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        n = len(moves)\n",
    "        if n % 2 == 0 and n < 9:\n",
    "            if self.check(moves) == \"Draw\" or self.check(moves) == 0:\n",
    "                return \"Pending\"\n",
    "            else:\n",
    "                return \"B\"\n",
    "        elif n % 2 == 1 and n < 9:\n",
    "            # print(\"self check\", self.check(moves))\n",
    "            if self.check(moves) == \"Draw\" or self.check(moves) == 0:\n",
    "                return \"Pending\"\n",
    "            else:\n",
    "                return \"A\"\n",
    "        else:\n",
    "            return self.check(moves)\n",
    "    \n",
    "    def check(self, moves):\n",
    "        board = [[0] * 3 for i in range(3)]\n",
    "        for i in range(len(moves)):\n",
    "            x= moves[i][0]\n",
    "            y = moves[i][1]\n",
    "            if i % 2 == 0:\n",
    "                board[x][y] = \"A\"\n",
    "            else:\n",
    "                board[x][y] = \"B\"\n",
    "        found = 1     \n",
    "        for i in range(3):\n",
    "            begin = board[i][0]\n",
    "            found = 1\n",
    "            for j in range(1, 3):\n",
    "                if board[i][j] != begin:\n",
    "                    found = 0\n",
    "                    break\n",
    "            if found == 1:\n",
    "                return begin\n",
    "    \n",
    "        for i in range(3):\n",
    "            begin = board[0][i]\n",
    "            found = 1\n",
    "            for j in range(1, 3):\n",
    "                if board[j][i] != begin:\n",
    "                    found = 0\n",
    "                    break\n",
    "            if found == 1:\n",
    "                return begin\n",
    "        print(board)\n",
    "        if board[0][0] == board[1][1] == board[2][2] and board[0][0] != 0:\n",
    "            return board[0][0]\n",
    "        elif board[0][2] == board[1][1] == board[2][0] and board[0][0] != 0:\n",
    "            return board[0][2]\n",
    "        else:\n",
    "            return \"Draw\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        wins = [\n",
    "            [(0, 0), (0, 1), (0, 2)],\n",
    "            [(1, 0), (1, 1), (1, 2)],\n",
    "            [(2, 0), (2, 1), (2, 2)],\n",
    "            [(0, 0), (1, 0), (2, 0)],\n",
    "            [(0, 1), (1, 1), (2, 1)],\n",
    "            [(0, 2), (1, 2), (2, 2)],\n",
    "            [(0, 0), (1, 1), (2, 2)],\n",
    "            [(0, 2), (1, 1), (2, 0)],\n",
    "        ]\n",
    "\n",
    "        def checkwin(S):\n",
    "            for win in wins:\n",
    "                flag = True\n",
    "                for pos in win:\n",
    "                    if pos not in S:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        A, B = set(), set()\n",
    "        for i, (x, y) in enumerate(moves):\n",
    "            if i % 2 == 0:\n",
    "                A.add((x, y))\n",
    "                if checkwin(A):\n",
    "                    return \"A\"\n",
    "            else:\n",
    "                B.add((x, y))\n",
    "                if checkwin(B):\n",
    "                    return \"B\"\n",
    "        \n",
    "        return \"Draw\" if len(moves) == 9 else \"Pending\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def examine(self):\n",
    "        def ast(rcs):\n",
    "            ls = [self.board[r][c] for (r, c) in rcs]\n",
    "            return all([i == ls[0] for i in ls]) and ls[0] != ' '\n",
    "            \n",
    "        for r in range(3):\n",
    "            if ast([(r, 0), (r, 1), (r, 2)]):\n",
    "                return r, 0\n",
    "        for c in range(3):\n",
    "            if ast([(0, c), (1, c), (2, c)]):\n",
    "                return 0, c\n",
    "        if ast([(0, 0), (1, 1), (2, 2)]):\n",
    "            return 1, 1\n",
    "        if ast([(0, 2), (1, 1), (2, 0)]):\n",
    "            return 1, 1\n",
    "        \n",
    "        return False\n",
    "                \n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        self.board = [[' ', ' ', ' '], [' ', ' ', ' '], [' ', ' ', ' ']]\n",
    "        \n",
    "        smap = {\n",
    "            True: 'X',\n",
    "            False: 'O'\n",
    "        }\n",
    "        turn_A = True\n",
    "        for m in moves:\n",
    "            r, c = m\n",
    "            self.board[r][c] = smap[turn_A]\n",
    "            # print(self.board)\n",
    "            rs = self.examine()\n",
    "            if rs != False:\n",
    "                return 'A' if self.board[rs[0]][rs[1]] == 'X' else 'B'\n",
    "            turn_A = not turn_A\n",
    "            \n",
    "        return 'Draw' if len(moves) == 9 else 'Pending'\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        A = moves[0::2]\n",
    "        B = moves[1::2]\n",
    "        a = sum([2**(i*3+j) for i,j in A])\n",
    "        b = sum([2**(i*3+j) for i,j in B])\n",
    "        \n",
    "        check = [448, 56, 7, 292, 146, 73, 273, 84]\n",
    "        \n",
    "        for c in check: \n",
    "            if a&c == c:\n",
    "                return \"A\"\n",
    "            if b&c == c:\n",
    "                return \"B\"\n",
    "            \n",
    "        if len(moves) == 9:\n",
    "            return \"Draw\"\n",
    "        return \"Pending\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gameOver(self, grid):\n",
    "        for i in range(3):\n",
    "            if grid[i][0] != None and grid[i][0] == grid[i][1] and grid[i][1] == grid[i][2]:\n",
    "                return grid[i][0]\n",
    "            if grid[0][i] != None and grid[0][i] == grid[1][i] and grid[1][i] == grid[2][i]:\n",
    "                return grid[0][i]\n",
    "        if grid[0][0] != None and grid[0][0] == grid[1][1] and grid[1][1] == grid[2][2]:\n",
    "            return grid[0][0]\n",
    "        if grid[0][2] != None and grid[0][2] == grid[1][1] and grid[1][1] == grid[2][0]:\n",
    "            return grid[0][2]\n",
    "        return None\n",
    "\n",
    "    def tictactoe(self, moves) -> str:\n",
    "        grid = [([None] * 3) for _ in range(3)]\n",
    "        for i in range(len(moves)):\n",
    "            if i % 2 == 0:\n",
    "                grid[moves[i][0]][moves[i][1]] = 'A'\n",
    "            else:\n",
    "                grid[moves[i][0]][moves[i][1]] = 'B'\n",
    "            if i >= 4:\n",
    "                res = self.gameOver(grid)\n",
    "                if res != None:\n",
    "                    return res\n",
    "        return 'Draw' if len(moves) >= 9 else 'Pending'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        m = {1:\"A\",2:\"B\"}\n",
    "        data = [[0] * 3 for _ in range(3)]\n",
    "        i = 2\n",
    "        for item in moves:\n",
    "            if i == 1:\n",
    "                i = 2\n",
    "            else:\n",
    "                i = 1\n",
    "            data[item[0]][item[1]] = i\n",
    "\n",
    "        x,y = moves[-1]\n",
    "        if data[0][y] == data[1][y] and data[0][y] == data[2][y] and data[0][y] == i:\n",
    "            return m[i]\n",
    "        if data[x][0] == data[x][1] and data[x][0] == data[x][2] and data[x][0] == i:\n",
    "            return m[i]\n",
    "        if x == y and data[0][0] == data[1][1] and data[0][0] == data[2][2]:\n",
    "            return m[i]\n",
    "        if (x,y) in {(2,0),(1,1),(0,2)}  and data[2][0] == data[1][1] and data[2][0] == data[0][2]:\n",
    "            return m[i]\n",
    "        if len(moves) == 9:\n",
    "            return \"Draw\"\n",
    "        return \"Pending\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        win_way=[[[0,0],[0,1],[0,2]],\n",
    "                [[0,0],[1,0],[2,0]],\n",
    "                [[2,0],[2,1],[2,2]],\n",
    "                [[0,2],[1,2],[2,2]],\n",
    "                [[0,0],[1,1],[2,2]],\n",
    "                [[0,1],[1,1],[2,1]],\n",
    "                [[0,2],[1,1],[2,0]],\n",
    "                [[1,0],[1,1],[1,2]],\n",
    "                ]\n",
    "        A_path=moves[::2]\n",
    "        B_path=moves[1::2]\n",
    "        for i in range(len(win_way)):\n",
    "            A_win,B_win=0,0\n",
    "            for i in win_way[i]:\n",
    "                if i in A_path:\n",
    "                    A_win+=1\n",
    "                if i in B_path:\n",
    "                    B_win+=1\n",
    "            if A_win==3:\n",
    "                return \"A\"\n",
    "            if B_win==3:\n",
    "                return \"B\"\n",
    "        if len(moves)==9:\n",
    "            return \"Draw\"\n",
    "        return \"Pending\"\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        wins = [\n",
    "            [(0, 0), (0, 1), (0, 2)],\n",
    "            [(1, 0), (1, 1), (1, 2)],\n",
    "            [(2, 0), (2, 1), (2, 2)],\n",
    "            [(0, 0), (1, 0), (2, 0)],\n",
    "            [(0, 1), (1, 1), (2, 1)],\n",
    "            [(0, 2), (1, 2), (2, 2)],\n",
    "            [(0, 0), (1, 1), (2, 2)],\n",
    "            [(0, 2), (1, 1), (2, 0)],\n",
    "        ]\n",
    "\n",
    "        def checkwin(S):\n",
    "            for win in wins:\n",
    "                flag = True\n",
    "                for pos in win:\n",
    "                    if pos not in S:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        A, B = set(), set()\n",
    "        for i, (x, y) in enumerate(moves):\n",
    "            if i % 2 == 0:\n",
    "                A.add((x, y))\n",
    "                if checkwin(A):\n",
    "                    return \"A\"\n",
    "            else:\n",
    "                B.add((x, y))\n",
    "                if checkwin(B):\n",
    "                    return \"B\"\n",
    "        \n",
    "        return \"Draw\" if len(moves) == 9 else \"Pending\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "关于输赢问题，只需判断moves中的最后一步对应的棋手X是否能赢，否则X不可能下了最后一步。\n",
    "m*m的网格，有m*2+2种赢棋方式，用count数组记录每种方式中已经包含的X的棋子数，\n",
    "当达到m后，表示X赢；否则判断是Draw还是Pending\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    chess = 3\n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        n = len(moves)\n",
    "        count = [0] * (2*self.chess + 2)\n",
    "        for i in range(n-1, -1, -2):\n",
    "            # 该步棋对行的影响\n",
    "            count[moves[i][0]] += 1\n",
    "            # 该步棋对列的影响\n",
    "            count[moves[i][1] + self.chess] += 1\n",
    "            # 该步棋对主对角线的影响\n",
    "            if moves[i][0] == moves[i][1]:\n",
    "                count[-2] += 1\n",
    "            # 该步棋对副对角线的影响\n",
    "            if moves[i][0] + moves[i][1] == self.chess - 1:\n",
    "                count[-1] += 1\n",
    "            # 判断是否已经赢得比赛\n",
    "            if self.checkWin(count):\n",
    "                return 'A' if n % 2 else 'B'\n",
    "        return 'Draw' if n == self.chess ** 2 else 'Pending'\n",
    "\n",
    "    \n",
    "    def checkWin(self, arr):\n",
    "        for v in arr:\n",
    "            if v == self.chess:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        a = set()\n",
    "        b = set()\n",
    "        import queue\n",
    "        def check(a):\n",
    "            if ((0,0)) in a and ((1,1)) in a and ((2,2)) in a:\n",
    "                return True\n",
    "            if ((2,0)) in a and ((1,1)) in a and ((0,2)) in a:\n",
    "                return True\n",
    "            if ((0,0)) in a and ((0,1)) in a and ((0,2)) in a:\n",
    "                return True\n",
    "            if ((1,0)) in a and ((1,1)) in a and ((1,2)) in a:\n",
    "                return True\n",
    "            if ((2,0)) in a and ((2,1)) in a and ((2,2)) in a:\n",
    "                return True\n",
    "            if ((0,0)) in a and ((1,0)) in a and ((2,0)) in a:\n",
    "                return True\n",
    "            if ((0,1)) in a and ((1,1)) in a and ((2,1)) in a:\n",
    "                return True\n",
    "            if ((0,2)) in a and ((1,2)) in a and ((2,2)) in a:\n",
    "                return True\n",
    "            return False\n",
    "        for i,v in enumerate(moves):\n",
    "            if i % 2 == 0:\n",
    "                a.add((v[0],v[1]))\n",
    "            else:\n",
    "                b.add((v[0],v[1]))\n",
    "            if check(a):\n",
    "                return 'A'\n",
    "            if check(b):\n",
    "                return 'B'\n",
    "        if len(moves) == 9:      \n",
    "            return 'Draw'\n",
    "        else:\n",
    "            return \"Pending\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "class Solution(object):\n",
    "    def tictactoe(self, moves):\n",
    "        A = moves[::2]\n",
    "        B = moves[1::2]\n",
    "        for a,b,c in itertools.permutations(A, 3):\n",
    "            if (b[1] - a[1])*(c[0] - a[0]) == (c[1] - a[1])*(b[0] - a[0]):\n",
    "                return \"A\"\n",
    "        for a,b,c in itertools.permutations(B, 3):\n",
    "            if (b[1] - a[1])*(c[0] - a[0]) == (c[1] - a[1])*(b[0] - a[0]):\n",
    "                return \"B\"\n",
    "        \n",
    "        if len(A) + len(B) == 9:\n",
    "            return \"Draw\"\n",
    "        else:\n",
    "            return \"Pending\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        if len(moves) < 5:\n",
    "            return 'Pending'\n",
    "        A = moves[::2]\n",
    "        B = moves[1::2]\n",
    "        wins = [[[0,0],[0,1],[0,2]],\n",
    "        [[1,0],[1,1],[1,2]],\n",
    "        [[2,0],[2,1],[2,2]],\n",
    "        [[0,0],[1,0],[2,0]],\n",
    "        [[0,1],[1,1],[2,1]],\n",
    "        [[0,2],[1,2],[2,2]],\n",
    "        [[0,0],[1,1],[2,2]],\n",
    "        [[0,2],[1,1],[2,0]]]\n",
    "\n",
    "        for i in wins:\n",
    "            if i[0] in A and i[1] in A and i[2] in A:\n",
    "                return \"A\"\n",
    "            if i[0] in B and i[1] in B and i[2] in B:\n",
    "                return \"B\"\n",
    "        if len(moves) < 9:\n",
    "            return \"Pending\"\n",
    "        else:\n",
    "            return \"Draw\"\n",
    "\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        if len(moves)<5:\n",
    "            return \"Pending\"\n",
    "        sum=1\n",
    "        list=[[\"\",\"\",\"\"],[\"\",\"\",\"\"],[\"\",\"\",\"\"]]  \n",
    "        for i in moves:\n",
    "            if sum%2==1:\n",
    "                list[i[0]][i[1]]='X'\n",
    "            else:\n",
    "                list[i[0]][i[1]]='O'\n",
    "            sum+=1\n",
    "        if list[0][0]=='X' and list[0][1]=='X' and list[0][2]=='X':\n",
    "            return \"A\"\n",
    "        elif list[1][0]=='X' and list[1][1]=='X' and list[1][2]=='X':\n",
    "            return \"A\"\n",
    "        elif list[2][0]=='X' and list[2][1]=='X' and list[2][2]=='X':\n",
    "            return \"A\"\n",
    "        elif list[0][0]=='X' and list[1][1]=='X' and list[2][2]=='X':\n",
    "            return \"A\"\n",
    "        elif list[0][2]=='X' and list[1][1]=='X' and list[2][0]=='X':\n",
    "            return \"A\"\n",
    "        elif list[0][0]=='X' and list[1][0]=='X' and list[2][0]=='X':\n",
    "            return \"A\"\n",
    "        elif list[0][1]=='X' and list[1][1]=='X' and list[2][1]=='X':\n",
    "            return \"A\"\n",
    "        elif list[0][2]=='X' and list[1][2]=='X' and list[2][2]=='X':\n",
    "            return \"A\"\n",
    "        elif list[0][0]=='O' and list[0][1]=='O' and list[0][2]=='O':\n",
    "            return \"B\"\n",
    "        elif list[1][0]=='O' and list[1][1]=='O' and list[1][2]=='O':\n",
    "            return \"B\"\n",
    "        elif list[2][0]=='O' and list[2][1]=='O' and list[2][2]=='O':\n",
    "            return \"B\"\n",
    "        elif list[0][0]=='O' and list[1][1]=='O' and list[2][2]=='O':\n",
    "            return \"B\"\n",
    "        elif list[0][2]=='O' and list[1][1]=='O' and list[2][0]=='O':\n",
    "            return \"B\"\n",
    "        elif list[0][0]=='O' and list[1][0]=='O' and list[2][0]=='O':\n",
    "            return \"B\"\n",
    "        elif list[0][1]=='O' and list[1][1]=='O' and list[2][1]=='O':\n",
    "            return \"B\"\n",
    "        elif list[0][2]=='O' and list[1][2]=='O' and list[2][2]=='O':\n",
    "            return \"B\"\n",
    "        if len(moves)<9:\n",
    "            return \"Pending\"\n",
    "        elif len(moves)==9:\n",
    "            return \"Draw\"\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        wins = [\n",
    "            [(0, 0), (0, 1), (0, 2)],\n",
    "            [(1, 0), (1, 1), (1, 2)],\n",
    "            [(2, 0), (2, 1), (2, 2)],\n",
    "            [(0, 0), (1, 0), (2, 0)],\n",
    "            [(0, 1), (1, 1), (2, 1)],\n",
    "            [(0, 2), (1, 2), (2, 2)],\n",
    "            [(0, 0), (1, 1), (2, 2)],\n",
    "            [(0, 2), (1, 1), (2, 0)],\n",
    "        ]\n",
    "\n",
    "        def checkwin(S):\n",
    "            for win in wins:\n",
    "                flag = True\n",
    "                for pos in win:\n",
    "                    if pos not in S:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        A, B = set(), set()\n",
    "        for i, (x, y) in enumerate(moves):\n",
    "            if i % 2 == 0:\n",
    "                A.add((x, y))\n",
    "                if checkwin(A):\n",
    "                    return \"A\"\n",
    "            else:\n",
    "                B.add((x, y))\n",
    "                if checkwin(B):\n",
    "                    return \"B\"\n",
    "\n",
    "        return \"Draw\" if len(moves) == 9 else \"Pending\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        wins = [\n",
    "            [[0, 0], [0, 1], [0, 2]],\n",
    "            [[1, 0], [1, 1], [1, 2]],\n",
    "            [[2, 0], [2, 1], [2, 2]],\n",
    "            [[0, 0], [1, 0], [2, 0]],\n",
    "            [[0, 1], [1, 1], [2, 1]],\n",
    "            [[0, 2], [1, 2], [2, 2]],\n",
    "            [[0, 0], [1, 1], [2, 2]],\n",
    "            [[0, 2], [1, 1], [2, 0]],\n",
    "        ]\n",
    "\n",
    "        def checkwin(S):\n",
    "            for win in wins:\n",
    "                flag = True\n",
    "                for pos in win:\n",
    "                    if pos not in S:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        A, B = [], []\n",
    "        for i, [x, y] in enumerate(moves):\n",
    "            if i % 2 == 0:\n",
    "                A.append([x, y])\n",
    "                if checkwin(A):\n",
    "                    return \"A\"\n",
    "            else:\n",
    "                B.append([x, y])\n",
    "                if checkwin(B):\n",
    "                    return \"B\"\n",
    "        \n",
    "        return \"Draw\" if len(moves) == 9 else \"Pending\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        # 傻瓜写法\n",
    "        b = [[0]*3 for _ in range(3)]\n",
    "        for i, (x, y) in enumerate(moves):\n",
    "            b[x][y] = 'B' if i & 1 else 'A'\n",
    "        for l in b:\n",
    "            if l.count('A') == 3:\n",
    "                return 'A'\n",
    "            if l.count('B') == 3:\n",
    "                return 'B'\n",
    "        for l in zip(*b):\n",
    "            if l.count('A') == 3:\n",
    "                return 'A'\n",
    "            if l.count('B') == 3:\n",
    "                return 'B'\n",
    "        if b[0][0] == b[1][1] == b[2][2] == 'A' or b[0][2] == b[1][1] == b[2][0] == 'A':\n",
    "            return 'A'\n",
    "        if b[0][0] == b[1][1] == b[2][2] == 'B' or b[0][2] == b[1][1] == b[2][0] == 'B':\n",
    "            return 'B'\n",
    "        return 'Draw' if len(moves) == 9 else 'Pending'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        a = moves[::2]\n",
    "        b = moves[1::2]\n",
    "        if ([1, 1] in a) and (([2, 2] in a and [0, 0] in a) or ([1, 2] in a and [1, 0] in a) or ([2, 0] in a and [0, 2] in a) or ([0, 1] in a and [2, 1] in a)) or ([1, 2] in a and [2, 2] in a and [0, 2] in a) or ([1, 0] in a and [0, 0] in a and [2, 0] in a) or ([0, 1] in a and [0, 0] in a and [0, 2] in a) or ([2, 1] in a and [2, 2] in a and [2, 0] in a):\n",
    "            return 'A'\n",
    "        if ([1, 1] in b) and (([2, 2] in b and [0, 0] in b) or ([1, 2] in b and [1, 0] in b) or ([2, 0] in b and [0, 2] in b) or ([0, 1] in b and [2, 1] in b)) or ([1, 2] in b and [2, 2] in b and [0, 2] in b) or ([1, 0] in b and [0, 0] in b and [2, 0] in b) or ([0, 1] in b and [0, 0] in b and [0, 2] in b) or ([2, 1] in b and [2, 2] in b and [2, 0] in b):\n",
    "            return 'B'\n",
    "        if len(moves) < 9:\n",
    "            return 'Pending'\n",
    "        else:\n",
    "            return 'Draw'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, moves: List[List[int]]) -> str:\n",
    "        n = len(moves)\n",
    "        if n <= 4: # A和B步数都少于3\n",
    "            return \"Pending\"\n",
    "        tmp = [[0 for i in range(3)] for i in range(3)] # 创建棋盘保存信息，1代表A，2代表B\n",
    "        for i in range(0,n,2): # 记录A下的棋\n",
    "            x,y = moves[i]\n",
    "            tmp[x][y] = 1\n",
    "        for i in range(1,n,2): # 记录B下的棋\n",
    "            x,y = moves[i]\n",
    "            tmp[x][y] = 2\n",
    "            \n",
    "        for i in range(3):\n",
    "            # 判断行是否有玩家获胜\n",
    "            s1 = list(set(tmp[i])) \n",
    "            if len(s1) == 1:\n",
    "                if s1[0] == 1:\n",
    "                    return 'A'\n",
    "                elif s1[0] == 2:\n",
    "                    return 'B'\n",
    "\n",
    "            # 判断列是否有玩家获胜\n",
    "            s2 = set()\n",
    "            for j in range(3): \n",
    "                s2.add(tmp[j][i])\n",
    "            s2 = list(s2)\n",
    "            if len(s2) == 1:\n",
    "                if s2[0] == 1:\n",
    "                    return 'A'\n",
    "                elif s2[0] == 2:\n",
    "                    return 'B'\n",
    "\n",
    "        # 判断对角线是否有玩家获胜\n",
    "        s = tmp[1][1]\n",
    "        if s != 0:\n",
    "            if tmp[0][0] == tmp[2][2] == s:\n",
    "                return 'A' if s == 1 else 'B'\n",
    "            if tmp[0][2] == tmp[2][0] == s:\n",
    "                return 'A' if s == 1 else 'B'\n",
    "                \n",
    "        # 发现没有玩家获胜便判断是平局还是游戏未结束\n",
    "        if n == 9:\n",
    "            return \"Draw\"\n",
    "        else:\n",
    "            return \"Pending\"\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
